// 下标从1开始
// 第一个参数是传入数组的类型
// 第二个参数是所需统计的和的类型
template<class T, class ST = T>
struct Sum2D {
	using i64 = long long;

	Sum2D(const vector<vector<T>> &v) {
		int n = v.size(), m = v[0].size();
		sum_.resize(n);
		for (int i = 0; i < n; i++) {
			sum_[i].resize(m, 0);
		}
		for (int i = 1; i < n; i++) {
			for (int j = 1; j < m; j++) {
				sum_[i][j] = sum_[i][j - 1] + sum_[i - 1][j] - sum_[i - 1][j - 1] + v[i][j];
			}
		}
	}

	ST query(const int x1, const int y1, const int x2, const int y2) {
		return sum_[x2][y2] - sum_[x1 - 1][y2] - sum_[x2][y1 - 1] + sum_[x1 - 1][y1 - 1];
	}
	vector<vector<ST>> sum_;
};
int main() {
	vector<vector<int>> s(4, vector<int>(4, 0));
	for (int i = 1;i <= 3; i++) {
		for (int j = 1; j <= 3; j++) {
			s[i][j] = i * 3 + j;
			cout << s[i][j] << ' ';
		}
		cout << '\n';
	}
	Sum2D<int> sum(s);
	cout << sum.query(1, 1, 2, 3) << endl;
	cout << sum.query(1, 1, 3, 3) << endl;
	Sum2D<int, long long> sum2(s);
	cout << sum.query(1, 1, 2, 3) << endl;
	cout << sum.query(1, 1, 3, 3) << endl;
	return 0;
}